package RemoveDuplicateLetters;


import java.util.Stack;

public class Solution {
    public String removeDuplicateLetters(String s) {
        StringBuilder result=new StringBuilder();
        Stack<Character> stack=new Stack<>();
        int[] lastLoc=new int[30];
        boolean[] bo=new boolean[30];
        for (int i=0;i<s.length();i++)
        	lastLoc[s.charAt(i)-'a']=i;
        for (int i=0;i<s.length();i++)
        {
        	char ch=s.charAt(i);
            if (bo[ch-'a']==true) continue;
            else{
        	while (stack.empty()==false)
        	   if ((stack.peek()>ch) && (i<lastLoc[stack.peek()-'a']))
        		   bo[stack.pop()-'a']=false;
        	   else break;
        	   stack.push(ch);
        	   bo[ch-'a']=true;
            }
        }
        bo=new boolean[30];
        getResult(result,stack,bo);
        return result.toString();
        
    }
    private void getResult(StringBuilder result, Stack<Character> stack, boolean[] bo) {
		if (stack.isEmpty()==false) {
			char ch=stack.pop();
			getResult(result,stack,bo);
			if (bo[ch-'a']==false)
				result.append(ch);
			    bo[ch-'a']=true;
		}
	}
	public static void main(String args[]) {
		String s="abacb";
		Solution so=new Solution();
		System.out.println(so.removeDuplicateLetters(s));
	}
}
